package com.nuo.laboratory.dataStructure;

import java.util.Arrays;
import java.util.Collections;

/**
 * 数组
 *
 * @author LGC
 * @date 2022/3/28 14:15
 */
public class MyArray {
    /**
     * 数组中心索引
     */
    public int pivotIndex(int[] nums) {
        // [1, 7, 3, 6, 5, 6]
        int length = nums.length;
        if (length == 1) {
            return 0;
        }
        // 中心索引
        int midIndex = -1;

        for (int i = 0; i < length; i++) {
            // 前半段值
            int preRs = 0;
            // 后半段值
            int afterRs = 0;
            if (i == 0) {
                for (int j = i + 1; j < length; j++) {
                    afterRs = afterRs + nums[j];
                }
                if (preRs == afterRs) {
                    midIndex = 0;
                    break;
                }
            } else {
                for (int j = 0; j < i; j++) {
                    preRs = preRs + nums[j];
                }
                for (int j = i + 1; j < length; j++) {
                    afterRs = afterRs + nums[j];
                }
                if (preRs == afterRs) {
                    midIndex = i;
                    break;
                }
            }

        }

        return midIndex;
    }

    /**
     * 寻找数组中心索引
     */
    public int pivotIndex2(int[] nums) {
        // [1, 7, 3, 6, 5, 6]
        // sum = leftSum + rightSum +nums[i]
        int sum = 0, leftSum = 0;

        for (int num : nums) {
            sum += num;
        }
        for (int i = 0; i < nums.length; i++) {
            if (leftSum == (sum - leftSum - nums[i])) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }


    /**
     * 有序数组搜索插入位置
     * 如果存在返回当前下标
     * 如果不存在返回插入的下标
     */
    public int searchInsert(int[] nums, int target) {
        // 1 2 3 4 5 6 7 8 9
        // 0 1 2 3 4 5 6 7 8
        //target=-1 mid = 0 + 4 = 4 left= 0 right = 3   4
        //target=-1 mid = 0 + 1 = 1 left= 0 right = 0   1
        //target=-1 mid = 0 + 0 = 0 left= 0 right = -1  0

        // 二分法
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            // 防止 left+right 整型溢出
            int mid = (left + right) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] ints = new int[]{2, 1, -1};
        MyArray myArray = new MyArray();
        System.out.println(myArray.pivotIndex(ints));


        int[] sorts = new int[]{1, 2, 5, 6, 8, 5, 3, 7, 9};
        System.out.println(Arrays.toString(sorts));
        // bubbling sort
//        for (int i = sorts.length - 1; i >= 0; i--) {
//            for (int j = 0; j < i ; j++) {
//                if (sorts[i] < sorts[j]) {
//                    int temp = sorts[i];
//                    sorts[i] = sorts[j];
//                    sorts[j] = temp;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(sorts));

        // select sort
//        for (int i = 0; i < sorts.length - 1; i++) {
//            for (int j = i + 1; j < sorts.length - 1; j++) {
//                if (sorts[j] < sorts[i]) {
//                    int temp = sorts[i];
//                    sorts[i] = sorts[j];
//                    sorts[j] = temp;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(sorts));

        for (int i = 1; i < sorts.length - 1; i++) {
            for (int j = 0; j < i; j++) {
//                if(sorts[j]>)
            }
        }
        
        System.out.println(Arrays.toString(sorts));
    }
}
